package leetcode_600;

/**
 *@author 周杨
 *OptimalDivision_553 给定一个数组 相邻的元素必须除 取得某种运算使得其值最大
 *describe:用动归加回溯 AC 80%
 *2018年9月13日 下午1:41:52
 */
public class OptimalDivision_553 {
	public static void main(String[] args) {
		OptimalDivision_553 test=new OptimalDivision_553();
		System.out.println(test.optimalDivision1(new int[] {1000,100,10,2}));
	}
	
	 public String optimalDivision(int[] nums) {
		 int n = nums.length;
	        if(n == 0) return "";
	        if(n == 1) return String.valueOf(nums[0]);// one num
	        if(n == 2) return String.valueOf(nums[0] + "/" + nums[1]);// two nums
	        StringBuffer sb = new StringBuffer(nums[0] + "");
	        sb.append("/(" + nums[1]);
	        for(int i = 2; i < n; i++) { //n >= 3, res = x1 /(x2/x3/x4/.../xn)
	            sb.append("/" + nums[i]);
	        }
	        sb.append(")");
	        return sb.toString();   
	 }
	 
	 /**
	 * describe:动态规划做返回数组
	 * 2018年9月13日 下午1:40:56
	 */
	public double optimalDivision1(int[] nums) {
	       return help(nums,new double[nums.length][nums.length],0,nums.length-1);
	 }
	 
	 public double help(int nums[],double dp[][],int left,int right) {
		 if(dp[left][right]!=0)
			 return dp[left][right];
		 if(left==right) {
			 dp[left][left]=nums[left];
			 return nums[left];
		 }
		 double max=Double.MIN_VALUE;
		 for(int i=left;i<right;++i) {
			 max=Math.max(max, help(nums,dp,left,i)/help(nums,dp,i+1,right));
		 }
		 dp[left][right]=max;
		 return max;
	 }
}
